import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
 * @lc app=leetcode.cn id=438 lang=java
 *
 * [438] 找到字符串中所有字母异位词
 *
 * https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/description/
 *
 * algorithms
 * Medium (39.57%)
 * Likes:    189
 * Dislikes: 0
 * Total Accepted:    13.9K
 * Total Submissions: 35.1K
 * Testcase Example:  '"cbaebabacd"\n"abc"'
 *
 * 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
 *
 * 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
 *
 * 说明：
 *
 *
 * 字母异位词指字母相同，但排列不同的字符串。
 * 不考虑答案输出的顺序。
 *
 *
 * 示例 1:
 *
 *
 * 输入:
 * s: "cbaebabacd" p: "abc"
 *
 * 输出:
 * [0, 6]
 *
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
 *
 *
 * 示例 2:
 *
 *
 * 输入:
 * s: "abab" p: "ab"
 *
 * 输出:
 * [0, 1, 2]
 *
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
 *
 *
 */

// @lc code=start
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int len = p.length();
        Map<Character, Integer> map = new HashMap<>();
        for(char ch : p.toCharArray()) {
            if(!map.containsKey(ch)) {
                map.put(ch, 1);
            } else {
                int value = map.get(ch);
                map.put(ch, ++value);
            }
        }
        for(int i=0; i<s.length() - len + 1;i++) {
            Map<Character, Integer> m = new HashMap<>(map);
            boolean flag = true;
            for(char ch : s.substring(i, i+len).toCharArray()) {
                if(!m.containsKey(ch)) {
                    flag = false;
                    break;
                } else {
                    int value = m.get(ch);
                    if(--value == 0) {
                        m.remove(ch);
                    } else {
                        m.put(ch, value);
                    }
                }
            }
            if(flag) {
                res.add(i);
            }
        }
        return res;
    }
}
// @lc code=end

